package 动态规划;

public class 最长公共子串 {
	public static void main(String[] args) {
		System.out.println(lcs1("ABCBA", "OUYBA"));
	}
	
	/**
	 * dp(i, j)表示以str1[i - 1]和str2[j - 1]为结尾的最长公共子串
	 */
	public static int lcs(String str1, String str2) {
		if (str1 == null || str1.length() == 0
				|| str2 == null || str2.length() == 0) return 0;
		char[] chars1 = str1.toCharArray();
		char[] chars2 = str2.toCharArray();
		int[][] dp = new int[chars1.length + 1][chars2.length + 1];
		int max = 0;
		for (int i = 1; i <= chars1.length; i++) {
			for (int j = 1; j <= chars2.length; j++) {
				if (chars1[i - 1] == chars2[j - 1]) {
					dp[i][j] = dp[i - 1][j - 1] + 1;
				}
				max = Math.max(max, dp[i][j]);
			}
		}
		return max;
	}
	
	/**
	 * 优化: 一维数组
	 */
	public static int lcs1(String str1, String str2) {
		if (str1 == null || str1.length() == 0
				|| str2 == null || str2.length() == 0) return 0;
		char[] chars1 = str1.toCharArray();
		char[] chars2 = str2.toCharArray();
		char[] rowsChars = chars1, colsChars = chars2;
		if (chars1.length < chars2.length) {
			rowsChars = chars2;
			colsChars = chars1;
		}
		int[] dp = new int[colsChars.length + 1];
		int max = 0;
		for (int i = 1; i <= rowsChars.length; i++) {
			int cur = 0;
			for (int j = 1; j <= colsChars.length; j++) {
				int leftTop = cur;
				cur = dp[j];
				if (rowsChars[i - 1] == colsChars[j - 1]) {
					dp[j] = leftTop + 1;
				} else {
					dp[j] = 0;
				}
				max = Math.max(max, dp[j]);
			}
		}
		return max;
	}
}
